package offer;

public class offer46 {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int num = 12258;
        int ans = solution.translateNum(num);
        Solution2 solution2 = new Solution2();
        int num2 = 26;
        int ans2 = solution2.translateNum(num2);
    }
    //滚动数组优化
    static class Solution {
        public int translateNum(int num) {
            String src = String.valueOf(num);
            int p = 0, q = 0, r = 1;
            for (int i = 0; i < src.length(); ++i) {
                p = q;
                q = r;
                r = 0;
                r += q;
                if (i == 0) {
                    continue;
                }
                String pre = src.substring(i - 1, i + 1);
                if (pre.compareTo("25") <= 0 && pre.compareTo("10") >= 0) {
                    r += p;
                }
            }
            return r;
        }
    }

    static class Solution2 {
        public int translateNum(int num) {
            String s = String.valueOf(num);
            int[] dp = new int[s.length()+2];
            dp[0] = 0;
            dp[1] = 1;
            //dp[2]才代表第一个数字有几种翻译方法
            for(int i = 2; i < dp.length; i++){
                if(i == 2){
                    dp[i] = dp[i-1];
                    continue;
                }
                String pre = s.substring(i-3, i-1);
                if(pre.compareTo("25") <= 0 && pre.compareTo("10") >= 0){
                    dp[i] = dp[i-1] + dp[i-2];
                } else {
                    dp[i] = dp[i-1];
                }
            }
            return dp[dp.length-1];
        }
    }
}
